1. Technical Field
The present disclosure relates to a technology for arranging a transmission schedule for a traffic flow that runs through a plurality of routers connected together through a distributed bus, in a semiconductor integrated circuit including such a bus.
2. Description of the Related Art
There are various methods for controlling the transfer of data through a semiconductor integrated circuit including a bus. FIGS. 35A and 35B illustrate exemplary known transfer control methods for a semiconductor integrated circuit. FIG. 35A illustrates an example of a centralized bus control. In a known integrated circuit that performs such a centralized bus control, a number of bus masters and a memory are usually connected together with a single bus, and accesses to the memory by the respective bus masters are arbitrated by an arbiter. By adopting such a configuration, data can be transferred while avoiding traffic flow interference between the bus masters and the memory. However, as the functionality of an integrated circuit has been further improved and as the number of cores in an integrated circuit has been further increased these days, the scale of the circuit has become even larger and the traffic flow through the transmission path has gotten even more complicated. As a result, it has become increasingly difficult to design an integrated circuit by such a centralized bus control.
Meanwhile, semiconductor integrated circuits with distributed buses have been developed one after another lately by introducing connection technologies in parallel computers and/or network control technologies. FIG. 35B illustrates an example of such a distributed bus control. In a semiconductor integrated circuit with distributed buses, a number of routers R are connected together with multiple buses. Recently, people have been working on a so-called “Network on Chip (NoC)” in which traffic flows in a large-scale integrated circuit are transferred through a number of distributed buses by adopting the distributed bus control such as the one shown in FIG. 35B.
FIG. 36 illustrates an exemplary configuration for a router for use in an NoC, parallel computers, an Asynchronous Transfer Mode (ATM) network, and so on. The data to be transferred (i.e., traffic data) is divided into a number of small units such as packets or cells, each of which is transferred to its destination node by way of multiple routers. The router shown in FIG. 36 includes Input Ports #0 and #1, two buffers #0 and #1 that are associated with these two input ports #0 and #1, respectively, Output Ports #0 and #1, and a crossbar switch that connects together the respective input buffers and the respective output ports. The router shown in FIG. 36 further includes an arbiter which performs a control operation by changing connection of the crossbar switch according to the destination of data. The data that has been input to this router through the Input Ports #0 and #1 is temporarily stored in the buffers #0 and #1. Each of these buffers #0 and #1 includes a plurality of virtual channels (VCs), which are connected in parallel with each other, and different sets of data can be processed in parallel on an input port basis.
The crossbar switch is a switch for determining an exclusive connection between each input port and its associated output port. In this description, the “exclusive connection” refers to a situation where not more than one input port is connected to one output port.
The exclusive connection between an input port and its associated output port via the crossbar switch is also arbitrated by an arbiter. By getting the crossbar switch turned by the arbiter in this manner, the router transfers the data that is stored in the buffers to a destination.
FIG. 37 illustrates an exemplary flow of packets that are transmitted from bus masters to memories via multiple routers. In the example illustrated in FIG. 37, two bus masters B0 and B1 are connected to two memories M0 and M1 via multiple routers R0, R1, R2 and R3 that are connected together in series. Each of these routers R0, R1, R2 and R3 has four virtual channels. In this example, traffic flows T0 and T1 are supposed to be transmitted from the bus master B0 to the memory M0 and from the bus master B1 to the memory M1, respectively, in the same mixture.
In FIG. 37, illustration of virtual channels that are provided for each input port is omitted for the sake of simplicity. Even though each of these routers can actually be connected to an even larger number of routers, bus masters or memories, only those four routers that are connected together in series are shown in FIG. 37 for the sake of simplicity. Also, in order to distinguish those traffic flows T0 and T1 easily, the virtual channels are supposed to be sequentially allocated to the traffic flows T0 and T1 from top to bottom and from bottom to top, respectively, in each router. It should be noted that the method shown in FIG. 37 is just an exemplary method for allocating virtual channels and there are various other methods for allocating virtual channels on a packet by packet basis.
The bus master B0 sends packets to the memory M0, while the bus master B1 sends packets to the memory M1. Each of those packets sent from each bus master is divided into smaller units called “flits”, which can be each transmitted in one cycle. And the packets are transferred to the destination memory on a flit by flit basis. On receiving a flit, a router processes that flit by performing the processing steps of: (1) storing the flit on a virtual channel specified, (2) determining to what router the flit needs to be transferred next, (3) determining on which virtual channel the flit will need to be stored in the next router, and then (4) sending the flit to the next router. By getting theses four processing steps done by each router, flits are sent to their destination one after another. And when all of those flits are delivered to their destination, they will be combined together to form the original single packet again.
In the example illustrated in FIG. 37, the router R0 adjacent to the bus masters B0 and B1 (1) stores the flits received from those bus masters in the virtual channels that were specified by the bus masters when the flits were sent. In this case, if the given flits form part of different packets, then those flits are stored on different virtual channels. Next, the router R0 (2) determines, by reference to the address information attached to the flit stored and on a virtual channel basis, to what router each of those flits needs to be transferred next. In the example illustrated in FIG. 37, the router R1 is supposed to be chosen as the destination of the flits transferred for each of the virtual channels. Subsequently, the router R0 (3) determines, on a virtual channel basis, on which virtual channel the flit will need to be stored in the next router R1. And once the next router R1 and the virtual channel to store the data in the next router R1 are determined on a virtual channel basis, the router R0 (4) sends the flits to that router R1.
Likewise, each of the other routers R1, R2 and R3 also (1) stores the flit that has been received from the previous router on the virtual channel specified, (2) determines to what router the flit needs to be transferred next, (3) determines on which virtual channel the flit will need to be stored in the next router, and then (4) transfers the flit to the next router or the destination memory. In this manner, data is transferred from multiple bus masters to multiple destination memories.
In a transfer system that uses the known router shown in FIG. 37, if there is a heavy transfer load, then competition may sometimes arise between flits to be delivered to different destinations when each router performs the processing steps (3) and (4). And once the competition arises, the packets may be delivered to the destination in a different order from the one in which they were sent. Or the time delay may be significantly different from one traffic flow to another. As a result, a decline will be caused in the quality of transfer.
That is why it is necessary to maintain the order in which packets have been sent and to minimize an increase in time delay or jitter for each traffic flow. For that purpose, a so-called “age-based” method has been proposed in U.S. Pat. No. 6,674,720, for example. According to that method, an estimated value called “age” is defined based on the time when a packet was transmitted and the number of hops that the packet has made (i.e., the number of routers that the packet has passed through). And according to the “age-based” method, a packet with the maximum (or minimum) age is supposed to be sent first.